Digital topology

Digital topology deals with properties and features of two-dimensional (2D) or three-dimensional (3D) digital images that correspond to topological properties (e.g., connectedness) or topological features (e.g., boundaries) of objects.

Concepts and results of digital topology are used to specify and justify important (low-level) image analysis algorithms, including algorithms for thinning, border or surface tracing, counting of components or tunnels, or region-filling.

History

Digital topology was first studied in the late 1960s by the computer image analysis researcher Azriel Rosenfeld (1931–2004), whose publications on the subject played a major role in establishing and developing the field. The term "digital topology" was itself invented by Rosenfeld, who used it in a 1973 publication for the first time.

A related work called the grid cell topology, which could be considered as a link to classic combinatorial topology, appeared in the book of Pavel Alexandrov and Heinz Hopf, Topologie I (1935). Rosenfeld et al. proposed digital connectivity such as 4-connectivity and 8-connectivity in two dimensions as well as 6-connectivity and 26-connectivity in three dimensions. The labeling method for inferring a connected component was studied in the 1970s. Theodosios Pavlidis (1982) suggested the use of graph-theoretic algorithms such as the depth-first search method for finding connected components. Vladimir A. Kovalevsky (1989) extended the Alexandrov–Hopf 2D grid cell topology to three and higher dimensions. He also proposed (2008) a more general axiomatic theory of locally finite topological spaces and abstract cell complexes formerly suggested by Ernst Steinitz (1908). It is the Alexandrov topology. The book from 2008 contains new definitions of topological balls and spheres independent of a metric and numerous applications to digital image analysis.

In the early 1980s, digital surfaces were studied. David Morgenthaler and Rosenfeld (1981) gave a mathematical definition of surfaces in three-dimensional digital space. This definition contains a total of nine types of digital surfaces. The digital manifold was studied in the 1990s. A recursive definition of the digital k-manifold was proposed intuitively by Chen and Zhang in 1993. Many applications were found in image processing and computer vision.

Basic results

A basic (early) result in digital topology says that 2D binary images require the alternative use of 4- or 8-adjacency or "pixel connectivity" (for "object" or "non-object" pixels) to ensure the basic topological duality of separation and connectedness. This alternative use corresponds to open or closed sets in the 2D grid cell topology, and the result generalizes to 3D: the alternative use of 6- or 26-adjacency corresponds to open or closed sets in the 3D grid cell topology. Grid cell topology also applies to multilevel (e.g., color) 2D or 3D images, for example based on a total order of possible image values and applying a 'maximum-label rule' (see the book by Klette and Rosenfeld, 2004).

Digital topology is highly related to combinatorial topology. The main differences between them are: (1) digital topology mainly studies digital objects that are formed by grid cells (the cells of integer lattices), rather than more general cell complexes, and (2) digital topology also deals with non-Jordan manifolds.

A combinatorial manifold is a kind of manifold which is a discretization of a manifold. It usually means a piecewise linear manifold made by simplicial complexes. A digital manifold is a special kind of combinatorial manifold which is defined in digital space i.e. grid cell space.

A digital form of the Gauss–Bonnet theorem is: Let M be a closed digital 2D manifold in direct adjacency (i.e., a (6,26)-surface in 3D). The formula for genus is

$g=1+(M_{5}+2M_{6}-M_{3})/8$,

where $M_{i}$ indicates the set of surface-points each of which has i adjacent points on the surface (Chen and Rong, ICPR 2008). If M is simply connected, i.e., $g=0$, then $M_{3}=8+M_{5}+2M_{6}$. (See also Euler characteristic.)

See also

• Digital geometry
• Combinatorial topology
• Computational geometry
• Computational topology
• Topological data analysis
• Topology
• Discrete mathematics
• Geospatial topology

References

• Herman, Gabor T. (1998). Geometry of Digital Spaces. Applied and Numerical Harmonic Analysis. Boston, MA: Birkhäuser Boston, Inc. ISBN 978-0-8176-3897-9. MR 1711168.
• Kong, Tat Yung; Rosenfeld, Azriel, eds. (1996). Topological Algorithms for Digital Image Processing. Elsevier. ISBN 0-444-89754-2.
• Voss, Klaus (1993). Discrete Images, Objects, and Functions in $\mathbb {Z} ^{n}$. Algorithms and Combinatorics. Vol. 11. Berlin: Springer-Verlag. doi:10.1007/978-3-642-46779-0. ISBN 0-387-55943-4. MR 1224678.
• Chen, L. (2004). Discrete Surfaces and Manifolds: A Theory of Digital-Discrete Geometry and Topology. SP Computing. ISBN 0-9755122-1-8.
• Klette, R.; Rosenfeld, Azriel (2004). Digital Geometry. Morgan Kaufmann. ISBN 1-55860-861-3.
• Morgenthaler, David G.; Rosenfeld, Azriel (1981). "Surfaces in three-dimensional digital images". Information and Control. 51 (3): 227–247. doi:10.1016/S0019-9958(81)90290-4. MR 0686842.
• Pavlidis, Theo (1982). Algorithms for graphics and image processing. Lecture Notes in Mathematics. Vol. 877. Rockville, MD: Computer Science Press. ISBN 0-914894-65-X. MR 0643798.
• Vladimir A. Kovalevsky. (2008). Geometry of Locally Finite Spaces. Berlin: Publishing House Dr. Baerbel Kovalevski. 2008. ISBN 978-3-9812252-0-4.